package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         110,
		Discription: "判断是否为平衡二叉树",
		Level:       1,
		Labels: map[string]int{
			"递归":   1,
			"二叉树":  1,
			"回溯": 1,
		},
	})
}

// IsBalanced 本质上还是求最大深度，只不过左子树的深度和右子树的深度之差大于1的时候返回-1，表示不平衡了，然后一路传上去
//  @param root 
//  @return bool 
func IsBalanced(root *ds.TreeNode) bool {
    var depth func(*ds.TreeNode) int
	depth = func(node *ds.TreeNode) int {
		if node == nil {
			return 0
		}

		leftDepth := depth(node.Left)
		rightDepth := depth(node.Right)
		if leftDepth == -1 || rightDepth == -1 || leftDepth-rightDepth > 1 || rightDepth-leftDepth > 1 {
			return -1
		}

		return max(leftDepth, rightDepth) + 1
	}

	return depth(root) != -1
}